A cache is a relatively high-speed, small, local memory which is used to provide a local storage (a buffer store) for frequently accessed memory locations of a larger, relatively slow, main memory (a backing store). By storing the information or a copy of the information locally, the cache is able to intercept memory references and handle them directly without transferring the request to the main memory over the system bus. The result is lower traffic on the memory bus and decreased latency on the CPU bus to the requesting processor.
The above-referenced U.S. Pat. No. 5,210,845 discloses a cache controller which has a tag RAM which is configured into two ways, each way including tag and valid-bit storage for associatively searching the directory for cache data-array addresses. The external cache memory is organized such that both ways are simultaneously available to a number of available memory modules in the system to thereby allow access to the ways to occur in parallel with the tag lookup.
The above-referenced U.S. Pat. No. 5,339,399 discloses a method and means for managing complex timing cycles in the controller of U.S. Pat. No. 5,210,845.
In a buffer/backing store memory hierarchy, requested data may not currently reside in the higher-speed buffer store and so access has to be made to the backing store to retrieve the data. Since it is necessary to make space for the new data in the buffer, data at some location in the buffer must be displaced by the new data. The new data then replaces data at a chosen location in the buffer store and the data occupying that location is displaced, the assumption being that the just fetched data will probably be needed again. Choosing what location to displace is done by making the assumption that the data most recently used (MRU), i.e. most recently added to the buffer, should be retained since it will probably be needed again. In contradistinction, the data location least recently used (LRU) probably is no longer needed and can be safely removed from the buffer and if needed again a duplicate back-up copy can be fetched from the backing store. A pointer, called an LRU pointer, is maintained that always points to the next location chosen by the logic to be replaced. How that LRU pointer is chosen will greatly affect the efficiency of the system by increasing or decreasing the number of accesses that must be made to the backing store over a given period of time.
In conventional buffer/backing store systems, a least recently used (LRU) pointer points to the data in the buffer that is the least recently used and this is the data that is replaced by new data from the backing store. In the controller described in U.S. Pat. No. 5,210,845 there are two sectors for each way, which means that there are two lines of data at a given set address, but only one line will be filled at any one time. Therefore, one line could have valid data while the other line may not have valid data. Since valid data can be placed in only one line at a time, when the data is put in a line, then that line contains the most recently used data and a conventional LRU algorithm would always designate that the LRU pointer should not be pointing to it. But this would not make efficient use of space in the two sector arrangement described above.
It is therefore an object of the present invention to provide a method and means for updating an LRU pointer in a controller for a data cache in which there are two sectors per way.